package problem.year2021.january;

import java.util.*;

/**
 * 在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
 * <p>
 * 现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没
 * 这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
 * <p>
 * 示例一：
 * 你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？
 * 输入: [[0,2],[1,3]]
 * 输出: 3
 * 解释:
 * 时间为0时，你位于坐标方格的位置为 (0, 0)。
 * 此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
 * <p>
 * 等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置
 * 示例2:
 * <p>
 * 输入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
 * 输出: 16
 * 解释:
 * 0  1  2  3  4
 * 24 23 22 21  5
 * 12 13 14 15 16
 * 11 17 18 19 20
 * 10  9  8  7  6
 * <p>
 * 最终的路线用加粗进行了标记。
 * 我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的
 * <p>
 * 2 <= N <= 50.
 * grid[i][j] 是 [0, ..., N*N - 1] 的排列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/swim-in-rising-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class January30 {
    /**
     * 解法一，利用二分查找加广度遍历解决，可以把时长n想想成一个关口，给n设置一个阈值，其中left<n<right，如果n符合要求，则大于n的绝对符合要求；
     * 给right赋值，表示为n;再进行重复的遍历，直到left>=right
     */
    static class Solution1 {
        public int swimInWater(int[][] grid) {
            int N = grid.length;
            int left = 0, right = N * N - 1, ans = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (fun1(mid, grid)) {
                    ans = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return ans;
        }

        // 用来记录是否可以在n时长可以遍历整个图
        private boolean fun1(int n, int[][] grid) {
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            // 记录已经走过的点
            boolean[] booleans = new boolean[grid.length * grid[0].length];
            // 记录当前队列链表
            Stack<int[]> stack = new Stack<>();
            if (grid[0][0] < n) {
                stack.push(new int[]{0, 0});
                booleans[0] = true;
            }
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                int x = cell[0], y = cell[1];
                for (int i = 0; i < 4; ++i) {
                    int nx = x + dirs[i][0];
                    int ny = y + dirs[i][1];
                    if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid.length && !booleans[nx * grid.length + ny] && grid[nx][ny] <= n) {
                        stack.push(new int[]{nx, ny});
                        booleans[nx * grid.length + ny] = true;
                    }
                }
            }
            return booleans[booleans.length - 1];
        }
    }

    /**
     * 解法二：并查集求解 + 排序求解;
     * 可以这样考虑，没经过一个时刻，则此间可以联通的水位进行联通；设【0，0】点为根，
     */
    static class Solution {

        private int N;

        public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        public int swimInWater(int[][] grid) {
            this.N = grid.length;

            int len = N * N;
            // 下标：方格的高度，值：对应在方格中的坐标
            int[] index = new int[len];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    index[grid[i][j]] = getIndex(i, j);
                }
            }

            UnionFind unionFind = new UnionFind(len);
            for (int i = 0; i < len; i++) {
                int x = index[i] / N;
                int y = index[i] % N;

                for (int[] direction : DIRECTIONS) {
                    int newX = x + direction[0];
                    int newY = y + direction[1];
                    if (inArea(newX, newY) && grid[newX][newY] <= i) {
                        unionFind.union(index[i], getIndex(newX, newY));
                    }

                    if (unionFind.isConnected(0, len - 1)) {
                        return i;
                    }
                }
            }
            return -1;
        }

        private int getIndex(int x, int y) {
            return x * N + y;
        }

        private boolean inArea(int x, int y) {
            return x >= 0 && x < N && y >= 0 && y < N;
        }

        private class UnionFind {

            private int[] parent;

            public UnionFind(int n) {
                this.parent = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                }
            }

            public int root(int x) {
                while (x != parent[x]) {
                    parent[x] = parent[parent[x]];
                    x = parent[x];
                }
                return x;
            }

            public boolean isConnected(int x, int y) {
                return root(x) == root(y);
            }

            public void union(int p, int q) {
                if (isConnected(p, q)) {
                    return;
                }
                parent[root(p)] = root(q);
            }
        }
    }


    public static void main(String[] args) {
        // 输入 [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
        // 输出 16
        Solution1 solution1 = new Solution1();
        int[][] grid = new int[][]{{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 20}, {10, 9, 8, 7, 6}};
        System.out.println(solution1.swimInWater(grid));
    }
}
